package test3;

class BTNode{
    public char val;
    public BTNode left;//左孩子的引用
    public BTNode right;//右孩子的引用
    public BTNode(char val){
        this.val=val;
    }

}

public class BinaryTree {
    public BTNode root;//二叉树的根节点
    public BTNode createTree(){
        BTNode A=new BTNode('A');
        BTNode B=new BTNode('B');
        BTNode C=new BTNode('C');
        BTNode D=new BTNode('D');
        BTNode E=new BTNode('E');
        BTNode F=new BTNode('F');
        BTNode G=new BTNode('G');
        BTNode H=new BTNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        return A;
    }

    //前序遍历
    public void preOrder(BTNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //中序遍历
    public void inOrder(BTNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    //后续遍历
    public void lastOrder(BTNode root){
        if(root==null){
            return;
        }
        lastOrder(root.left);
        lastOrder(root.right);
        System.out.print(root.val+" ");
    }

    //获取叶子节点的个数
    int count1=0;
    public int getLeatNodeCount(BTNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null && root.right==null){
            count1++;
        }
        getLeatNodeCount(root.left);
        getLeatNodeCount(root.right);
        return count1;

    }


    //第k节点的个数
    public int getKLevelNodeCount(BTNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

    BTNode find(BTNode root,char val) {
        if(root==null) {
            return null;
        }
        if(root.val==val)  return root;
        find(root.left,val);

        find(root.right,val);

        return null;

    }






}
